// 给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

// 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

// 示例:

// X X X X
// X O O X
// X X O X
// X O X X
// 运行你的函数后，矩阵变为：

// X X X X
// X X X X
// X X X X
// X O X X
// 解释:

// 被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

#include <vector>
#include <queue>
using namespace std;

// 从边界上的'O'入手，把不需要变得'O'变成'$',
class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if (m == 0) return;
        int n = board[0].size();
        if (n == 0) return;
        for (int i{0}; i < m; ++i) {
            for (int j{0}; j < n; ++j) {
                if ((i == 0 || i == m-1 || j == 0 || j == n-1) && board[i][j] == 'O') // 边界上的'O'
                DFS(board, i, j);
            }
        }
        for (int i{0}; i < m; ++i) {
            for (int j{0}; j < n; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == '$') board[i][j] = 'O';
            }
        }
    }
    void DFS(vector<vector<char>>& board, int i, int j) {
        int m = board.size();
        int n = board[0].size();
        if (board[i][j] == 'O') {
            board[i][j] = '$';
            if (i > 0 && board[i-1][j] == 'O')
                DFS(board, i-1, j);
            if (j < n-1 && board[i][j+1] == 'O')
                DFS(board, i, j+1);
            if (i < m-1 && board[i+1][j] == 'O')
                DFS(board, i+1, j);
            if (j > 0 && board[i][j-1] == 'O')
                DFS(board, i, j-1);
        }
    }
};

/* 深度优先搜索
标记所有和边界上的O相连的O，
时间复杂度：O(mn)
空间复杂度；O(mn)
*/
class Solution {
private:
    int m{0};
    int n{0};
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) {
            return;
        }
        m = board.size();
        n = board[0].size();
        for (int i{0}; i < m; ++i) {
            dfs(board, i, 0);   // 每一行第一个
            dfs(board, i, n-1); // 每一行最后一个
        }
        for (int j{1}; j < n-1; ++j) {
            dfs(board, 0, j);   // 每一列第一个
            dfs(board, m-1, j); // 每一列最后一个
        }
        for (int i{0}; i < m; ++i) {
            for (int j{0}; j < n; ++j) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O'; // 被标记的还要恢复成'O'
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X'; // 没有被标记的'O'是被包围的
                }
            }
        }
    }
    void dfs(vector<vector<char>>& board, int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') {
            return;
        }
        board[x][y] = 'A'; // 与边界上的'O'相连的'O'标记为'A'
        dfs(board, x+1, y);
        dfs(board, x-1, y);
        dfs(board, x, y+1);
        dfs(board, x, y-1);
    }
};

/* 广度优先搜索
标记所有和边界上的O相连的O，
时间复杂度：O(mn)
空间复杂度；O(mn)
*/
class Solution {
private:
    // 方向数组
    const int dx[4] = {1, -1, 0, 0};
    const int dy[4] = {0, 0, 1, -1};
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) {
            return;
        }
        int m = board.size();
        int n = board[0].size();
        queue<pair<int, int>> q{};
        for (int i{0}; i < m; ++i) {
            if (board[i][0] == 'O') {
                q.emplace(i, 0); // 第一列
            }
            if (board[i][n-1] == 'O') {
                q.emplace(i, n-1); // 最后一列
            }
        }
        for (int j{1}; j < n-1; ++j) {
            if (board[0][j] == 'O') {
                q.emplace(0, j); // 第一行
            }
            if (board[m-1][j] == 'O') {
                q.emplace(m-1, j); // 最后一行
            }
        }
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            board[x][y] = 'A';
            for (int i{0}; i < 4; ++i) {
                int mx = x + dx[i];
                int my = y + dy[i];
                if (mx < 0 || mx >= m || my < 0 || my >= n || board[mx][my] != 'O') {
                    continue;
                }
                q.emplace(mx, my);
            }
        }
        for (int i{0}; i < m; ++i) {
            for (int j{0}; j < n; ++j) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }
};